#include <bits/stdc++.h>
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;

typedef long long LL;

const int N = 400040;

struct Node {LL x, sum, num;} tl[N << 2], tr[N << 2];

int n, usd[N], num, t[N << 2];
LL a[N], b[N], sum;
map<LL, int> id;

Node operator + (Node x, Node y) {
    return {x.sum * y.num + x.x + y.x, x.sum + y.sum, x.num + y.num};
}

void updl(int x, int L, int R, int l, int tp) {
    if (L == R) {
        if (tp == -1) tl[x].x = tl[x].sum = tl[x].num = 0;
        else {
            tl[x].x = tl[x].sum = b[L];
            tl[x].num = 1;
        }
        return;
    }
    int mid = L + R >> 1;
    if (l <= mid) updl(ls, L, mid, l, tp);
    else updl(rs, mid + 1, R, l, tp);
    tl[x] = tl[ls] + tl[rs];
}

void updr(int x, int L, int R, int l, int tp) {
    if (L == R) {
        if (tp == -1) tr[x].x = tr[x].sum = tr[x].num = 0;
        else {
            tr[x].x = tr[x].sum = b[L];
            tr[x].num = 1;
        }
        return;
    }
    int mid = L + R >> 1;
    if (l <= mid) updr(ls, L, mid, l, tp);
    else updr(rs, mid + 1, R, l, tp);
    tr[x] = tr[rs] + tr[ls];
}

Node qryl(int x, int L, int R, int l) {
    if (l == 0) return {0, 0, 0};
    if (L == R) return tl[x];
    int mid = L + R >> 1;
    if (tl[ls].num >= l) return qryl(ls, L, mid, l);
    else return tl[ls] + qryl(rs, mid + 1, R, l - tl[ls].num);
}

Node qryr(int x, int L, int R, int l) {
    if (l == 0) return {0, 0, 0};
    if (L == R) return tr[x];
    int mid = L + R >> 1;
    if (tr[rs].num >= l) return qryr(rs, mid + 1, R, l);
    else return tr[rs] + qryr(ls, L, mid, l - tr[rs].num);
}

int main() {
    freopen("kte.in", "r", stdin);
    freopen("kte.out", "w", stdout);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= m; i++)
        id[b[i]] = i;
    for (int i = 1; i <= n; i++) {
        int idx = id[a[i]];
        if (usd[idx]) {
            usd[idx] = 0;
            updl(1, 1, m, idx, -1);
            updr(1, 1, m, idx, -1);
            sum -= a[i]; num--;
        } else {
            usd[idx] = 1;
            updl(1, 1, m, idx, 1);
            updr(1, 1, m, idx, 1);
            sum += a[i]; num++;
        }
        int l = 0, r = num / 2, pos1, pos2;
        while (l <= r) {
            int mid = l + r >> 1;
            Node ql = qryl(1, 1, m, mid + 1);
            Node qr = qryr(1, 1, m, mid);
            
            if (ql.sum > qr.sum) l = mid + 1;
            else r = mid - 1;
        }
        pos1 = r; l = num / 2 + 1, r = num - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            Node ql = qryl(1, 1, m, mid + 1);
            Node qr = qryr(1, 1, m, mid);
            // cout << "mid = " << mid << " " << ql.sum << " " << qr.sum << endl;
            if (ql.sum > qr.sum) r = mid - 1;
            else l = mid + 1;
        }
        pos2 = l;
        Node ql = qryl(1, 1, m, num);
        Node qr = qryr(1, 1, m, num - 1);
        // cout << "sum = " << sum << " " << qryl(1, 1, m, pos1 + 1).x << " " << pos1 << " " << pos2 << " " << ql.x << " " << qryl(1, 1, m, 1).sum << endl;
        printf("%lld\n", sum - ((qryl(1, 1, m, pos1 + 1).x + ql.x - qryl(1, 1, m, pos2).x) - (qryr(1, 1, m, pos1).x + qr.x - qryr(1, 1, m, pos2 - 1).x)));
    }
    return 0;
}